package main

func main() {
	
}

//你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
//
// 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1
//
// 给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
//
//
//
// 示例 1:
//
// 输入: 2, [[1,0]]
//输出: true
//解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
//
// 示例 2:
//
// 输入: 2, [[1,0],[0,1]
//输出: false
//解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
//
//
//
// 提示：
//
//
// 输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
// 你可以假定输入的先决条件中没有重复的边。
// 1 <= numCourses <= 10^5
//
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序
// 👍 437 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func canFinish(numCourses int, prerequisites [][]int) bool {
	var (
		edges = make([][]int, numCourses)
		indeg = make([]int, numCourses)
		result []int
	)

	for _, info := range prerequisites {
		// 节点i能指向edges[i]数组中的节点
		// [
		//	[] /*第0门课的先导课*/,
		//	[] /*第1门课的先导课*/,
		//	[] /*第2门课的先导课*/,
		// 	......
		// ]
		edges[info[1]] = append(edges[info[1]], info[0])
		// indeg是代表一个节点的入度
		indeg[info[0]]++
	}

	// q是广度优先搜索的队列
	q := []int{}
	for i := 0; i < numCourses; i++ {
		if indeg[i] == 0 {
			q = append(q, i)
		}
	}

	for len(q) > 0 {
		// 队列先进先出，所以取q[0]
		u := q[0]
		q = q[1:]
		// 队列中的节点肯定是入度为0的节点，所以可以加入到结果集中
		result = append(result, u)
		for _, v := range edges[u] {
			// 将u加入结果集中，相当于将u在图中去掉，u的先导课们的入度减一
			indeg[v]--
			// 某门先导课的入度为0则加入到队列中
			if indeg[v] == 0 {
				q = append(q, v)
			}
		}
	}
	// 如果最后结果集中有全部的节点，说明图是有向无环图，否则就是有向有环图
	return len(result) == numCourses
}
//leetcode submit region end(Prohibit modification and deletion)
